package com.iceph0x.algorithm.sort;

import java.util.Comparator;

import com.iceph0x.algorithm.framework.ISort;

public class MergeSort implements ISort {
    
    int[] heap;
    
    @Override
    public void sort(int[] data) {
        if (data == null || data.length < 2)
            return;
        
        if (heap == null || heap.length < data.length)
            heap = new int[data.length];
        synchronized (this) {
            mergeSort(data, 0, data.length - 1);
        }
    }

    private void mergeSort(int[] data, int low, int high) {
        if (low == high)
            return;
        int mid = (low + high >> 1) + 1;
        mergeSort(data, low, mid - 1);
        mergeSort(data, mid, high);
        
        int i = low, j = mid, index = 0;
        while (i < mid && j <= high) {
            if (data[i] < data[j])
                heap[index++] = data[i++];
            else
                heap[index++] = data[j++];
        }
        if (i < mid)
            System.arraycopy(data, i, heap, index, mid - i);
        else
            System.arraycopy(data, j, heap, index, high - j + 1);
        System.arraycopy(heap, 0, data, low, high - low + 1);
    }
    

    @Override
    public void sort(Object[] data, Comparator<Object> c) {
        // TODO Auto-generated method stub

    }

}
